\section{Verwendete mathematische Verfahren}
Dieses Kapitel wurde mit Hilfe des Buches \textit{Moderne Verfahren der Kryptographie}\cite{mod_kry} (Kapitel 8), \textit{Zahlentheorie für Einsteiger}\cite{zahlentheorie_fuer_einsteiger} (Kapitel 2), \textit{Kryptologie}\cite{kryptologie} (Kapitel 5) und \textit{RSA and public-key cryptography}\cite{rsa_and_public_key} (Appendix C) erarbeitet.\\[2ex]
%
Der RSA-Algorithmus baut grundsätzlich auf Primzahlen, der Modulo und Eulerschen Funktion, dem Satz von Euler und dem erweiterten euklidischen Algorithmus auf.\\
Im nächsten Abschnitt werden die einzelnen mathematischen Verfahren kurz in ihren Funktionen erläutert.\\
Wir werden für die beiden Primzahlen durchgehend die Variablen $p$ und $q$ verwenden. $N$ steht immer für das Produkt von $p \cdot q$. Die Variable $r$ wird für das Resultat der Modulo-Berechnungen verwendet. $e$ steht für den Verschlüsselungs-Exponenten und $d$ für den Entschlüsselungs-Exponenten.
%
\subsection{Modulo}
Modulo oder auch \textit{Division mit Rest} gibt den ganzzahligen Rest einer Division zweier natürlichen Zahlen an. Er wird beim RSA-Algorithmus bei der Berechnung des Entschlüsselungs-Exponenten sowie in der Verschlüsselung verwendet.\\
Modulo erklärt sich am Einfachsten an einem Beispiel:
%
\begin{equation*}
  21 \bmod(5) = 1
\end{equation*}
%
Es gilt herauszufinden, wie viel Mal 5 ganz in 21 vorhanden ist. Dafür teilen wir 21 durch 5 und schneiden den Dezimalrest ab. Um den ganzzahligen Rest zu berechnen subtrahieren wir von 21 das Produkt aus 4 mal 5.
%
\begin{flalign*}
  21 \colon 5 &= 4.2\\
  21 - 4 \cdot 5 &= 1\\
  21 &= 4 \cdot 5 + 1
\end{flalign*}
%Oder für den RSA Algorithmus veralgemeinert:
%\begin{equation}
%  \varphi(N) = q \cdot e + r
%  \label{eqn:mod_rsa}
%\end{equation}
%
\paragraph{Kongruent Modulo}
Kongruent Modulo bedeutet nichts anders, als dass zwei verschiedene Zahlen Modulo einer gleichen Zahl den selben Rest haben. Man sagt auch, dass sie in der gleichen Restklasse sind.\\
Als Beispiel nehmen wir die Zahlen 9 und 7 die Modulo 2 gerechnet werden.
%
\begin{flalign*}
  9 \bmod(2) &= 1 \\
  7 \bmod(2) &= 1  \\
  9 & \equiv 7 \bmod(2)
\end{flalign*}
%
%******************************************************************************
% Eulersche Funktion
%******************************************************************************
%Verbessern die Zahlen sind kleiner als die Zahl
\subsection{Eulersche Phi-Funktion}

Die Eulersche Funktion zählt die natürlichen, teilerfremden\footnote{Zwei Zahlen sind teilerfremd zueinander, wenn ihr grösster gemeinsamer Teiler 1 ist.}  Zahlen von n, die kleiner als n sind.\\
Für die Eulersche Funktion stellen die Primzahlen einen Spezialfall dar.
Primzahlen sind nur durch 1 und sich selbst ohne Rest teilbar. Somit ist das Resultat der die Eulerschen Funktion einer Primzahl p immer $p - 1$.\\
Um den privaten Schlüssel zu errechnen, muss man $\varphi(N)$ beziehungsweise $\varphi(pq)$ berechnen. Aus diesem Grund erläutern wir die Eulersche Funktion:
%
\begin{equation*}
  \varphi(p) = p - 1
\end{equation*}
%
Beispiel mit der Primzahl 17:
\begin{flalign*}
	\varphi(17) &= 17 - 1\\
	\varphi(17) &= 16\\
\end{flalign*}
Der grösste gemeinsame Teiler zweier Primzahlen ist immer 1.
Für die Eulersche Funktion auf zwei Primzahlen gilt:
\begin{equation}
  \varphi(pq) = \varphi(p) \cdot \varphi(q) = (p - 1) \cdot (q - 1)
  \label{eqn:eulersche_func}
\end{equation}
Der Beweis dafür liefert folgende Überlegung. Es gibt insgesamt $p \cdot q -1$ ganze Zahlen die kleiner sind als $p \cdot q$.\\
%TODO: Das stimmt irgendwie nicht ganz. Has umgschriebe, chasches nomol kontrolliere. Gruess Denis
%Es ist bei Primzahlen einfacher, die \textbf{nicht teilerfremden} Zahlen zu zählen und diese dann von allen möglichen Zahlen abzuziehen, als alle teilerfremden Zahlen zu zählen. Nicht teilerfremd zu p sind $(q - 1) \cdot p$ und für q gilt $ (p - 1) \cdot q$. \cite{kryptologie}\\
Es ist bei Primzahlen einfacher, die \textbf{nicht teilerfremden} Zahlen zu zählen und diese dann von allen möglichen Zahlen abzuziehen, als alle teilerfremden Zahlen zu zählen. Nicht Teilerfremd zu p sind $(q - 1)$ und für q gilt $ (p - 1) $. (siehe Kapitel 5 \cite{kryptologie} )\\
Als Formel geschrieben:
%
\begin{equation*}
  \begin{split}
    \varphi(pq) & = (p \cdot q - 1) - (p - 1) - (q - 1)  \\
     & = p \cdot q - 1 - p + 1 - q + 1  \\
     & = p \cdot q - q - p + 1  \\
     & = (p -1) \cdot (q - 1)
    \label{eqn:herleitung_eulersche_func}
  \end{split}
\end{equation*}
%
An einem Beispiel mit Primzahlen 17 und 7 ausgedrückt:
\begin{equation*}
  \begin{split}
    \varphi(7 \cdot 17) & = (7 \cdot 17 - 1) - (7 - 1) - (17 - 1)  \\
    \varphi(119) & = 118 - 6 - 16 \\
    & = (17 - 1) \cdot (7 - 1) \\    
    & = 96 \\
  \end{split}
\end{equation*}
%
% Satz von Euler
%=====================
%Verweis auf Buch Beutelspacher
\subsection{Satz von Euler}
Der Satz von Euler gewährleistet die korrekte Ver- und Entschlüsselung. Wir gehen hier nicht weiter auf den Satz von Euler ein und werden später beim Beweis nochmals auf ihn zurückkommen.\\
Der Satz von Euler sagt über zwei natürliche, teilerfremde Zahlen, hier $n$ und $m$, folgendes aus: (siehe Kapitel 5 \cite{kryptologie} und Kapitel 2 \cite{zahlentheorie_fuer_einsteiger})
%
\begin{equation}
  m^{\varphi(n)} \bmod(n) = 1
  \label{eqn:satz_von_euler}
\end{equation}
%
Nehmen wir für $n = 15$ und $m = 4$ und setzen Formel \ref{eqn:satz_von_euler} ein.
%
% Zeigen das varphi 15 = 8 ist
\begin{flalign*}
  4^{\varphi(15)} \bmod(15) = 1  \\
  4^8 \bmod(15) = 1 \\
  65536 \bmod(15) = 1 \\
  65536 -4369 \cdot 15 = 1
\end{flalign*}
%
%
% Kleiner Satz von Verma
%
%Wenn wir jetzt eine natürliche Zahl k nehmen, gilt für diese folgende Gleichung (Erleuterung siehe Buch \textit{Kryptologie}):
%
%\begin{equation}
%  \begin{split}
%    m^{1 + k \cdot \varphi(N)} \bmod(N)  &= m \cdot 1 \\
%    m \cdot m^{k \cdot \varphi(N)} \bmod(N) &= m \cdot 1
%    \label{eqn:satz_von_euler_erweitert}
%  \end{split}
%\end{equation}
%
%
%Hat man zwei verschiedene Primzahlen p und q und eine natürliche Zahl m, die kleiner ist als $p \cdot q$, dann gilt für jede natürliche Zahl k:
%
%\begin{equation}
%  m^{k \cdot (p - 1) \cdot (q - 1) +1} \bmod(p \cdot q) = m
%  \label{eqn:kleiner_satz_fermat}
%\end{equation}
%
%Dieser Satz wird in der Mathematik auch \textit{kleiner Satz von Fermat} genannt.
% Buch S 109 / 110
%
%******************************************************************************
% Euklidischer Algorithmus
%******************************************************************************
\subsection{Euklidischer Algorithmus}\label{euklidischer_Algorithmus}
Mit den Euklidischen Algorithmen lässt sich der grösste gemeinsame Teiler (ggT) zweier natürlichen Zahlen a und b berechnen. Es existiert das etwas ältere Subtraktionsverfahren und das moderne Modulo-Verfahren. Da das Subtraktions-Verfahren nicht die gleiche Effizienz hat wie das Subtraktionsverfahren, konzentrieren wir uns auf das Modulo-Verfahren. (siehe  Kapitel 2 \cite{zahlentheorie_fuer_einsteiger} und  Appendix C \cite{kryptographie})\\
%
Die Formel für das Modulo-Verfahren lautet:
%
\begin{equation}
  \label{eqn:euklidischer_algo}
  a = q \cdot b + r 
\end{equation}
%
Die Formel drückt die natürliche Zahl a als $ q \cdot b + den Rest $ aus. \\
Es gelten folgende Bedingungen:
\begin{equation*}
  0 \leq r \leq b - 1
\end{equation*}
\\
%
Für den RSA-Algorithmus ist es wichtig, dass wir zwei teilerfremde Zahlen $\varphi(N)$ und $e$ haben und erhalten dadurch folgende Formel:\\
%Auf den RSA-Algorithmus angewendet sieht die Formel folgendermassen aus:
\begin{equation}
  \label{eqn:euklidischer_algo_RSA}
  \varphi(N) = q \cdot e + r 
\end{equation}
%
Dabei sind $\varphi(N)$ und e die beiden Zahlen von denen wir den grössten gemeinsamen Teiler ausrechnen.
Wir gehen davon aus das $\varphi(N)$ grösser ist als e. Wäre das nicht der Fall, müsste $ e $ und $ \varphi(N) $  getauscht werden.
Zur Veranschaulichung nehmen wir zwei Zahlen $\varphi(N) = 839$ und $e = 199$ und setzen diese in unsere Gleichung ein.
\begin{enumerate}
  \item Schritt: Zahlen in Gleichung einsetzen, q und r ausrechnen.\\
    \begin{equation*}
      839 = 4 \cdot 199 + 43
    \end{equation*}
  \item Schritt: 199 als neues $\varphi(N)$ und 43 als neues e einsetzten und wieder q und r ausrechnen.\\
    \begin{equation*}
      199 = 4 \cdot 43 + 27
    \end{equation*}
\end{enumerate}
Den zweiten Schritt solange wiederholen bis man auf Rest 1 oder 0 kommt. Falls die Zahl 0 herauskommt, nehmen wir den Rest der vorangegangenen Gleichung als grössten gemeinsamen Teiler.\\
%
Ganzer Ablauf:
\begin{equation*}
  \begin{split}
    839 &= 4 \cdot 199 + 43\\
    199 &= 4 \cdot 43 + 27\\
    43 &= 1 \cdot 27 + 16\\
    27 &= 1 \cdot 16 + 11\\
    16 &= 1 \cdot 11 + 5\\
    11 &= 2 \cdot 5 + 1\\
    \label{eqn:euqulid_beweis}
  \end{split}
\end{equation*}
%
Der grösste gemeinsame Teiler von 839 und 199 ist 1. Sie sind daher teilerfremd. \\[2ex]
Um dieses Verfahren zu beweisen, gehen wir davon aus, dass $\varphi(N)$, e, r und q alles natürliche  % nicht negative 
Zahlen sind. Da wir im zweiten Schritt den grössten gemeinsamen Teiler von $e$ und r errechnet haben, kann man basierend auf Formel \ref{eqn:euklidischer_algo_RSA} folgende Behauptung aufstellen:
%
\begin{equation}
  ggT(\varphi(N),e) = ggT(e,r)
  \label{eqn:ggT}
\end{equation}
%
Nur der grösste gemeinsame Teiler von $\varphi(N)$ und $e$ teilt sowohl $\varphi(N)$ als auch e und r ohne Rest. Auf unser Beispiel angewendet ergibt das $ggT(839,199) \leq ggT(199,43)$.\\
Und es gilt: Nur der grösste gemeinsame Teiler von e und r teilt auch $\varphi(N)$ ohne Rest.\\
Das heisst: $ggT(199,43) \leq ggT(839,199)$.
Somit stimmen die beiden grössten gemeinsamen Teiler überein. (siehe Kapitel 2 \cite{zahlentheorie_fuer_einsteiger})\\[2ex]
Gehen wir zurück zu unserem Beispiel:
%
\begin{equation*}
 ggT(839,199) = ggT(199,43) = ggT(43,27) = ggT(27,16) = ggT(16,11) = ggT(11,5) = 1
\end{equation*}
%
%******************************************************************************
% Erweiterter Euklidischer Algorithmus
%******************************************************************************
\subsubsection{Erweiterter Euklidischer Algorithmus}
Der erweiterte Euklidische Algorithmus berechnet neben dem grössten gemeinsamen Teiler $r$ zweier natürlichen Zahlen a und b auch noch die dazugehörigen natürlichen Zahlen s und t, dass folgende Gleichung stimmt: (siehe Kapitel 5 \cite{kryptologie})
%
\begin{equation}
  ggT(a,b) = s \cdot a + t \cdot b
  \label{eqn:erw_euklid_algo}
\end{equation}
%
Auf den RSA-Algorithmus angewendet verwenden wir $ r = 1$ als grössten gemeinsamen Teiler. Nun suchen wir für die zwei natürlichen Zahlen $ e $ und $ \varphi(N) $ die dazugehörigen Zahlen d und k. 
%
\begin{equation}
  r = d \cdot e + k \cdot \varphi(N) 
  \label{eqn:erw_euklid_algo_RSA}
\end{equation}
%
Mit seiner Hilfe lässt sich der Entschlüsselungs-Exponent d berechnen, welchen wir für die Berechnung des privaten Schlüssels brauchen.\\
Dieser Algorithmus wird auch \textit{Vielfachsummendarstellung} genannt, denn um auf die Zahlen d und k zu kommen, muss man die Vielfachsummendarstellung anwenden.\\
Es handelt sich um eine erweiterte Form des Euklidischen Algorithmus.\\
Wir schreiben jetzt die Rechnung \ref{eqn:euqulid_beweis} so um, dass wir den Rest auf einer Seite isolieren.\\ 
\begin{equation}
  r = \varphi(N) - a \cdot e
  \label{eqn:form_erw_euklid}
\end{equation}
%
\begin{flalign*}
  43 &= 839 - 4 \cdot 199\\
  27 &= 199 - 4 \cdot 43\\
  16 &= 43 - 1 \cdot 27\\
  11 &= 27 - 1 \cdot 16\\
  5 &= 16 - 1 \cdot 11\\
  1 &= 11 - 2 \cdot 5
  \label{eqn:erw_euklid_10}
\end{flalign*}
%
% TODO: AUSSCHREIBEN
Man startet bei der untersten Zeile und ersetzt die Zahl, die den nächsten oberen Rest beschreibt, durch die Gleichung. Das heisst man ersetzt in der ersten Gleichung die Zahl $5$ mit dem Term $16 - 1 \cdot 11$. Das wiederholt man so lange, bis man die letzte Gleichung eingesetzt hat. 
Es ist zu beachten, dass auf der rechten Seite eine Summe aus zwei Produkten stehen bleibt.
%
\begin{flalign*}
  1  &= 11 - 2 \cdot 5 = 11 - 2 \cdot 16 + 2 \cdot 11 = 3 \cdot 11 - 2 \cdot 16 \\
  &= 3 \cdot 11 - 2 \cdot 16 = 3 \cdot 27 - 3 \cdot 1 \cdot 16 - 2 \cdot 16 = 3 \cdot 27 - 5 \cdot 16\\
  &= 3 \cdot 27 - 5 \cdot 16 = 3 \cdot 27 - 5 \cdot 43 + 5 \cdot 1 \cdot 27 = 8 \cdot 27 - 5 \cdot 43\\
  &= 8 \cdot 27 - 5 \cdot 43 = 8 \cdot 199 - 8 \cdot 4 \cdot 43 - 5 \cdot 43 = 8 \cdot 199 - 37 \cdot 43\\
  &= 8 \cdot 199 - 37 \cdot 43 = 8 \cdot 199 - 37 \cdot 839 + 37 \cdot 4 \cdot 199 = 156 \cdot 199 - 37 \cdot 839
\end{flalign*}
%
% Am Schluss erhalten wir die Formel
Am Schluss können wir unser Ergebnis in der Form $ r = d \cdot e + k \cdot \varphi(N)$ darstellen:
%
\begin{equation*}
 1 = 156 \cdot 199 + (-37) \cdot 839
 \label{eqn:erw_euklid_end}
\end{equation*}
%
Da der Entschlüsselungs-Exponent d und k vertauscht sein könnte, müssen wir die Gleichung in die \textbf{Modulare Inverse} umschreiben. Wir berechnen somit die Modulare Inverse von $\varphi(N)$ und $e$, damit $d$ jeweils positiv ist. \\
% Damit wir jetzt den Entschlüsselungs-Exponenten d bekommen, müssen wir die Gleichung in die Modulare Inverse umschreiben. Wir berechnen somit die Modulare Inverse von $\varphi(N)$ und e.\\
Die Formel der modularen Inverse auf den RSA-Algorithmus angewendet lautet:
\begin{equation*}
  e \cdot d \bmod(\varphi(N)) \equiv 1
  \label{eqn:modulare_inverse}
\end{equation*}
%
Wir gehen von Formel \ref{eqn:erw_euklid_end} aus und setzen den Term $(-37) \cdot 839$ auf die linke Seite.
%
\begin{equation*}
 1 + 37 \cdot 839 = 156 \cdot 199
\end{equation*}
Damit man den nächsten Schritt versteht, muss man wissen, dass die Gleichung
\begin{equation*}
  1 + k \cdot \varphi(N) = d \cdot e
\end{equation*}
mit Modulo ausgedrückt werden kann. (siehe Formel \ref{eqn:modulare_inverse}) 
\begin{equation*}
  1 \equiv d \cdot e \bmod(\varphi(N))
  \label{eqn:erw_eukl_fertig}
\end{equation*}
%
Aufgrund dessen können wir die Modulare Inverse von $\varphi(N)$ und e so ausdrücken:
%
\begin{equation*}
 1 \equiv 156 \cdot 199 \bmod(839)
\end{equation*}
Wir erhalten den Entschlüsselungs-Exponent $d = 156$.
%
%Um das zu beweisen schauen wir uns nochmal die Formel \ref{eqn:euklidischer_algo} an. Aus einer Vielfachsummendarstellung von $q$ und $r$, lässt sich dei Vielfachsummendarstellung von $p$ und $q$ ableiten. Man kann die Formel
%{eqn:ggT}
%\begin{equation*}
%  2 = x \cdot p + y \cdot q
%  \label{eqn:erw_eukl_fertig}
%\end{equation*}
%
%auch mit r und a darstellen.
%
%\begin{equation*}
%  2 = x \cdot r + y \cdot a
%\end{equation*}
%
%Jetzt setzen wir die Formel \ref{eqn:form_erw_euklid} anstatt r ein und erhalten diese Gleichung
%\begin{equation*}
%  2 = x \cdot (p - a \cdot q)  + y \cdot a = x \cdot p + (y - xa) \cdot q
%\end{equation*}
%
%Somit haben wie die Vielfachsummendarstellung für $p$ und $q$.
%
%\subsubsection{Modulare Inverse}
%Haben wir zwei natürliche, teilerfremde Zahlen, gibt es eine Zahl x, sodass die Formel
%
%\begin{equation*}
%  p \cdot x \bmod(q) \equiv 1
%\end{equation*}
%
%Es gibt zwei ganze Zahlen $x$ und $y$ sodass die Gleichung \ref{eqn:erw_eukl_fertig} entsteht.
%Weil $y cdot q$ durch $q$ teilbar ist, gibt es bei der Divison von $x \cdot p$ durch $q$ immer 1. Somit kann man sagen
%
%\begin{equation}
%  p \cdot x \bmod q = 1
%  \label{eqn:mod_inverse}
%\end{equation}
%
%Die Modulareinverse von zwei teilerfremden natürlichen Zahlen $p$ und $q$, errechnet man mit dem erweiterten Euklidischen Algorithmus. Dann ist $x$ die modulare Inverse von $p$ und $q$.
